The present invention relates to a parallel pseudo-random pattern generating method which derives p-bit parallel patterns from a pseudo-random pattern generator formed by an n-stage shift register each time the pattern generator is shifted k bit positions. The invention also pertains to a pseudo-random pattern generating device using such a parallel pseudo-random pattern generating method.
A pseudo-random bit sequence (PRBS, referred to also as a pseudo-random pattern) is used in various technical fields. For instance, it is used as a transmission signal for measuring the error rate of a transmission line or for spectrum spreading a transmission signal. The situation may sometimes arise where a pseudo-random pattern composed of a plurality of parallel bits is needed, for instance, as a random address sequence which is used to randomly read out the contents of a ROM. In FIG. 1A there is shown a conventional parallel pseudo-random pattern generator. From p shift stages of a pseudo-random pattern generator (hereinafter referred to as an n-stage PRBS generator) 11 formed by an n-stage shift register are extracted parallel p bits by a p-bit extraction part 12 and, upon each extraction, the n-stage PRBS generator 11 is shifted k bit positions. That is, each time p bits are needed, the n-stage PRBS generator 11 is shifted k bit positions and the p bits are taken out; alternatively, the n-stage PRBS generator 11 is shifted at all times and each time it is shifted k bit positions, p bits are latched in the p-bit extraction part 12. In general, it is preferable that k be chosen to be equal to or greater than p in order to prevent the current p-bit pattern from containing a bit or bits of the previous p-bit pattern. To use the extracted p bits as an address sequence to read out a memory, for example, is equivalent to accessing to the memory with a random address. In this way, the n-stage PRBS generator 11 may sometimes by shifted k bit positions in synchronization with the period of using the p bits.
When it is required to provide a pseudo-random pattern which maximizes the pattern repetition period, the pseudo-random pattern generator is so formed as to generate a so-called M-sequence pattern. In such an instance, the repetition period of the M-sequence pattern is 2.sup.n -1 bits. To make the values of the extracted p bit as random as possible, it is desirable that 2.sup.n -1 and k be mutually prime. If they are not mutually prime, then the values of p bits which are taken out with a period shorter than the 2.sup.n -1 bit period will be repeated, and hence the randomness of the p bit values will be impaired accordingly. For example, in the case where k is set to 3 and two bits "x.sub.3, x.sub.4 " are output in FIG. 1C, the "x.sub.3, x.sub.4 " bit outputs at t=1, 4, 7, 10 and 13 are "1, 1," "1, 0," "1, 0" and "0, 1," respectively; the occurrence rate of "1" is higher than that of "0" and outputs "0, 0" are not provided, instead the outputs "1, 0" are produced in succession.
As will be seen from the above, when the shift bit number k is not inappropriate, the transition of the values of p bits does not take place at random and is limited specifically to a set of fixed values. That is, it is desirable that p bits of the subsequent pattern be allowed to take 2.sup.p kinds of values based on the current values of p bits, but this is not guaranteed when the number k is not appropriate. The M-sequence pattern available from the n-stage PRBS generator 11 takes all possible values (except all zeros) once every period--this is regarded as ensuring the randomness of the p bit values. Yet, when the p bit values cannot take 2.sup.p kinds of values, the randomness is impaired.
For instance, consider a pseudo-random pattern generator using a four-stage shift register. As shown in FIG. 1B, four stages of D type flip-flops 14.sub.4 through 14.sub.1 are connected in series to form a shift register, which is driven by a clock CK that is fed to each of the flip-flops 14.sub.4 through 14.sub.1. The outputs from the last and first stages 14.sub.1 and 14.sub.4 are EXCLUSIVE ORed by an exclusive OR circuit 15, whose output is fed to the first stage 14.sub.4. The output from the last stage 14.sub.1 is provided as the M-sequence pseudo-random pattern. Letting the outputs from the shift stages 14.sub.1 through 14.sub.4 be represented by x.sub.1 through x.sub.4, the generating polynomial f(x) of this pseudo-random pattern is expressed by f(x)=x.sup.4 +x+1, and when initial values of x.sub.1 through x.sub.4 are all ones, the resulting bit sequences are such as shown in FIG. 1C.
In FIG. 1C, it is at time points t=1, 6, 14 and 15 that the outputs (x.sub.3, x.sub.4) go to (1, 1), and at t=2, 7, 15 and 1 after a one-bit shift of the register, the outputs (x.sub.3, x.sub.4) are (1, 0), (1, 0), (1, 1) and (1, 0), respectively. Hence, at a time point (t'=t+1) when the shift register is shifted one bit position after the outputs (x.sub.3, x.sub.4) go to (1, 1), there are only two kinds of values (1, 0) and (1, 1) which they are allowed to take. Similarly, when the shift register is shifted two bit positions (t'=t+2) after the outputs (x.sub.3, x.sub.4) go to (1, 1), there are four pairs of values (0, 1), (0, 0), (1, 1) and (1, 0) which the outputs (x.sub.3, x.sub.4) may take. Shifting the shift register two bit positions when the outputs (x.sub.3, x.sub.4) are (0, 1) or (1, 0), there are similarly four pairs of values that they can take. Shifting the shift register two bit positions when the outputs (x.sub.3, x.sub.4) are (0, 0), there are three pairs of values (1, 0), (0, 1) and (1, 1) that they may take--this is because the pseudo-random pattern does not take the value of all zeros.
It is desirable that the random number change from the current value to the next one with the same probability, whatever value it may take. In the case of the one-bit shift (k=1), however, one of the two bits always remains unchanged; hence, the randomness in this case is one-half of that in the case of the two-bit shift (k=2). To determine the most appropriate number k of bits to be shifted, it is customary in the prior art to check the number of values that the p-bit output is allowed to take for each number k as described above in respect of FIG. 1C and select the number k of bits that provides many values for the p-bit output. On this account, the conventional method becomes harder with an increase in the number n of shift stages.